#include <stdio.h>
#include <string.h>
#include <malloc.h>
using namespace std;
int kmp(char* str, char* sub) {
    int m = strlen(str), n = strlen(sub);
    int* next = (int*)malloc(sizeof(int) * n);
    memset(next, 0, sizeof(int) * n);
    // 求公共前后缀数组
    for (int i = 1, j = 0; i < n; ++i) {
        while (j > 0 && sub[i] != sub[j])
            j = next[j - 1];
        if (sub[i] == sub[j])
            ++j;
        next[i] = j;
    }
    // 用子串匹配主串
    for (int i = 0, j = 0; i < m; ++i) {
        while (j > 0 && str[i] != sub[j])
            j = next[j - 1];
        if (str[i] == sub[j])
            ++j;
        if (j == n)
            return i - j + 1;
    }
    return -1;
}
int main(void) {
    int ans = kmp((char*)"aabaab", (char*)"abaa");
    printf("ans = %d\n", ans);

    return 0;
}